import java.util.ArrayList;
import java.util.List;

class Solution {
    //电话号码的字母组合
    public List<String> ret;
    public StringBuilder path;
    public String[] hash;
    public List<String> letterCombinations(String digits) {

        hash = new String[10];
        hash[2] = "abc";
        hash[3] = "def";
        hash[4] = "ghi";
        hash[5] = "jkl";
        hash[6] = "mno";
        hash[7] = "pqrs";
        hash[8] = "tuv";
        hash[9] = "wxyz";
        ret = new ArrayList<>();
        if(digits.length() == 0) return ret;
        path = new StringBuilder();
        dfs(digits, 0);
        return ret;
    }
    public void dfs(String digits, int pos){
        //递归出口
        if(pos >= digits.length()){
            ret.add(path.toString());
            return;
        }

        int index = digits.charAt(pos) - '0';
        for(int i = 0; i < hash[index].length(); i++){
            path.append(hash[index].charAt(i));
            dfs(digits, pos + 1);
            //回溯
            path.delete(path.length() - 1, path.length());
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.letterCombinations("23");
    }
}